Section: New Results

Computer Algebra and Algorithmic Number Theory

The Elliptic Curve Discrete Logarithm Problem (ECDLP) has become the most attractive alternative to factoring for public key cryptography. Whereas subexponential factoring algorithms exist, solving the ECDLP in general can only be done in exponential time. Provided that a certain heuristic assumption holds, we present in [39] an index calculus algorithm solving ECDLP over any binary field ${𝔽}_q$ in time $O\left(2^{c{n}^{2/3}logn}\right)$, where $c$ is a small constant. Our algorithm follows the index calculus method that was first introduced by Semaev and later developed by Gaudry and Diem. In particular, the main step consists in decomposing points of the curve with respect to an appropriately chosen factor basis. This part can be nicely reformulated as a purely algebraic problem consisting in finding solutions to a multivariate polynomial $𝐟({𝐱}_{\mathbf{1}},...,{𝐱}_{𝐦})=\mathbf{0}$ such that all the variables ${𝐱}_{𝐢}$ belong to some vector subspace of ${𝔽}_q/{𝔽}_p$. We solve this problem by means of Gröbner basis techniques and analyse its complexity using the multihomogeneous structure of the equations. Even, if this paper is essentially theoretical and is not aiming for practical attacks, the new ideas developed here could be used to have practical attacks in the future. This of course represents a challenging open problem.